package basic.sort.violence;

/**
 * @author distantstar
 * @version 1.0
 * @date 2021
 * @description basic.sort.violence
 * @since JDK1.8
 *
 * 假设有排成一行的N个位置，记为1~N，N 一定大于或等于 2
 * 开始时机器人在其中的M位置上(M 一定是 1~N 中的一个)
 * 如果机器人来到1位置，那么下一步只能往右来到2位置；
 * 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
 * 如果机器人来到中间位置，那么下一步可以往左走或者往右走；
 * 规定机器人必须走 K 步，最终能来到P位置(P也是1~N中的一个)的方法有多少种
 * 给定四个参数 N、M、K、P，返回方法数。
 */
public class RobotWalk {
    private static int ways1(int n, int start, int aim, int k) {
        if (n < 2 || start < 1 || start > n || aim < 1 || aim > n || k < 1) {
            return -1;
        }
        return process1(start, k, aim, n);
    }

    /**
     * 暴力尝试
     * @param start 当前位置
     * @param k 需要走的步数
     * @param aim 目标位置
     * @param n 路径长度
     * @return 返回方法数
     */
    private static int process1(int start, int k, int aim, int n) {
        // 当步数走完时，判断此时的位置是否是目标位置
        if (k == 0) {
            return start == aim ? 1 : 0;
        }
        // 如果机器人来到1位置，那么下一步只能往右来到2位置；
        if (start == 1) {
            return process1(2, k - 1, aim, n);
        }
        // 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
        if (start == n) {
            return process1(n - 1, k - 1, aim, n);
        }

        return process1(start - 1, k - 1, aim, n) +
                process1(start + 1, k - 1, aim, n);
    }

    private static int ways2(int n, int start, int aim, int k) {
        if (n < 2 || start < 1 || start > n || aim < 1 || aim > n || k < 1) {
            return -1;
        }

        int[][] dp = new int[n + 1][k + 1];
        for (int i = 0; i <= n; i++){
            for (int j = 0; j <= k; j++){
                dp[i][j] = -1;
            }
        }

        return process2(start, k, aim, n, dp);
    }

    private static int process2(int start, int k, int aim, int n, int[][] dp) {
        if (dp[start][k] != -1) {
            return dp[start][k];
        }
        // 当步数走完时，判断此时的位置是否是目标位置
        if (k == 0) {
            dp[start][k] = start == aim ? 1 : 0;
            return dp[start][k];
        }
        // 如果机器人来到1位置，那么下一步只能往右来到2位置；
        if (start == 1) {
            dp[start][k] = process2(2, k - 1, aim, n, dp);
            return dp[start][k];
        }
        // 如果机器人来到N位置，那么下一步只能往左来到 N-1 位置；
        if (start == n) {
            dp[start][k] = process2(n - 1, k - 1, aim, n, dp);
            return dp[start][k];
        }

        dp[start][k] = process2(start - 1, k - 1, aim, n, dp) +
                process2(start + 1, k - 1, aim, n, dp);
        return dp[start][k];
    }

    private static int ways3(int n, int start, int aim, int k) {
        if (n < 2 || start < 1 || start > n || aim < 1 || aim > n || k < 1) {
            return -1;
        }

        int[][] dp = new int[n + 1][k + 1];
        dp[aim][0] = 1;
        for (int rest = 1; rest <= k; rest++) {
            dp[1][rest] = dp[2][rest - 1];
            for (int cur = 2; cur < n; cur++) {
                dp[cur][rest] = dp[cur - 1][rest - 1] + dp[cur + 1][rest - 1];
            }
            dp[n][rest] = dp[n - 1][rest - 1];
        }

        return dp[start][k];
    }

    public static void main(String[] args) {
        System.out.println(ways1(5, 2, 4, 6));
        System.out.println(ways2(5, 2, 4, 6));
        System.out.println(ways3(5, 2, 4, 6));
    }
}
